This invention relates to embedded coding techniques and more particularly to an embedded image coder with improved rate-distortion.
Embedded image coding improves coding performance and also allows a bitstream to be truncated at any point and still decode a reasonably good image. Some representative embedded coding techniques include the embedded zerotree wavelet coding (EZW) discussed in J. Shapiro, xe2x80x9cEmbedded image coding using zerotree of wavelet coefficientsxe2x80x9d, IEEE Trans. On Signal Processing, vol. 41, pp.3445-3462, December 1993, the set partitioning in hierarchical trees (SPIHT) discussed in A. Said, and W. Pearlman, xe2x80x9cA new, fast and efficient image codec based on set partitioning in hierarchical treesxe2x80x9d, IEEE Trans. On Circuit and System for Video Technology, Vol. 6, No. 3, June 1996, pp. 243-250 and the layered zero coding (LZC) discussed in, D Taubman and A. Zakhor, xe2x80x9cMultirate 3-D subband coding of videoxe2x80x9d, IEEE Trans. On Image Processing, Vol. 3, No. 5, September 1994, pp.572-588.
The ability to adjust the compression ratio by simply truncating the coding bitstream makes embedding attractive for a number of applications such as progressive image transmission, internet browsing, scalable image and video databases, digital cameras, low delay image communications, etc. Taking internet image browsing as an example, embedded coding requires storage on a server of only one copy of a high quality image. Depending on user demand, channel bandwidth conditions, and browser monitor quality, selectable amounts of the image bit stream can be delivered to the browser. At an early stage of browsing, images can be retrieved with coarse quality so that a user can quickly go through a large number of images before choosing one image of interest. The chosen image can then be fully downloaded with a better quality level. During the download process, the image quality is gradually refined. The user can terminate the download process as soon as the quality is satisfactory to discern the image.
Embedded coding allows the bitstream to be arbitrarily truncated. However, existing embedded coding techniques are not optimized at every truncation point in the bit stream. Thus, if the encoded bitstream is truncated at random points in the bit stream, the image produced by the bit stream up to the point of truncation does not necessarily produce optimal image quality.
It is known that a fixed rate coder achieves optimality if the rate-distortion (R-D) slopes of all coded coefficients are the same, T. M. Cover and J. A. Thomas, xe2x80x9cElements of information theoryxe2x80x9d, Chapter 13, John Wiley and Sons Inc, 1991. The criterion was used in rate control to adjust the quantization step size Q of each macroblocks, in which case the coding of video was optimal when the R-D slopes of all macroblocks were constant. See L.-J. Lin, A. Ortega and C.-C. J. Kuo, xe2x80x9cRate control using spline-interpolated R-D characteristicsxe2x80x9d, SPIE: Visual Communication and Image Processing, vol. 2727, Orlando, Fla., April 1996, pp. 111-122 and K. Ramchandran, A. Ortega and M. Vetterli, xe2x80x9cBit allocation for dependent quantization with applications to multiresolution and MPEG video codersxe2x80x9d, IEEE Trans. On Image Processing, Vol. 3, No. 5, September 1994, pp. 533-545.
Xiong and Ramchandran use the constant rate-distortion slope criterion to derive the optimal quantization for wavelet packet coding. Z. Xiong and K. Ramchandran, xe2x80x9cWavelet packet-based image coding using joint space-frequency quantizationxe2x80x9d, First IEEE International Conference on Image Processing, Austin, Tex., Nov. 13-16, 1994. However, Xiong and Ramchandran do not optimize rate-distortion optimization for embedded coders.
The R-D slopes of significance identification and refinement coding are different, and by placing the significance identification before the refinement coding, the coding efficiency can be improved. However, the improvement is limited since only the coding order of a few coefficients is effected. See Li, Cheng and Kuo J. Li, P. Cheng and C. -C. J. Kuo, xe2x80x9cOn the improvements of embedded zerotree wavelet (EZW) codingxe2x80x9d, SPIE: Visual Communication and Image Processing, vol. 2601, Taipei, Taiwan, May. 1995, pp. 1490-1501.
Thus, a need remains for an embedded coder that optimizes rate-distortion at many different truncation points in an encoded bit stream.
A rate-distortion optimised embedding (RDE) coder optimises rate-distortion performance by coding coefficients in order of their R-D slope. RDE allocates the available coding bits first to the coefficient with the steepest R-D slope, which indicates the largest distortion decrease per coding bit. The resultant RDE bitstream can be truncated at any point and still maintain an optimal R-D performance. To avoid the overhead of coding order transmission, an expected R-D slope is calculated by both the encoder and the decoder from previous RDE coded bits. A probability estimation table from a QM arithmetic coder allows the R-D slope to be derived using a lookup table operation. The RDE rate-distortion optimisation significantly improves the coding efficiency over a wide bit rate range.
The RDE embedded coding method digitizes the image and then transforms the image to form a set of coefficients each comprising multiple bits. The RDE coder repeatedly analyzes all the candidate bits before encoding individual bits. The candidate bits comprise one most significant unencoded bit from each coefficient. Individual rate-distortion values for the candidate bits represent a ratio of information content in the bit per cost in transmitting the bit. Selected bits are then encoded according to the associated distortion reduction values for the bits.
In one embodiment, one bit among the candidate bits having a maximum distortion reduction value is encoded. The candidate bits are updated comprising a next less significant bit in the encoded bit coefficient and the remaining unencoded candidate bits. The bit among the candidate bits with the highest distortion reduction value per coding bit is encoded next. The process is repeated until the RDE coder reaches a specified bit rate.
In another embodiment, a threshold value is set and the candidate bits having distortion reduction values greater than the threshold are encoded in each scan. The candidate bits are updated comprising a next less significant bit in the encoded bit coefficient and the remaining unencoded candidate bits. The threshold value is then reduced and a next set of unencoded candidate bits are processed. The candidate bits in the next set having distortion reduction values greater than the reduced threshold value are then encoded. The process is repeated until the RDE coder reaches the predetermined bit rate.